In data communications systems such as Asymmetric Digital Subscriber Lines (ADSL), noisy transmission lines can cause data to be corrupted or lost. In order to correct errors and recover lost data, additional error-checking data is often transmitted along with the transmitted data (payload data). The combination of a group of payload data bytes and the error-checking data for the group of payload data bytes is referred to as a codeword, or frame. The receiving end of the data transmission can determine if errors have occurred in a particular codeword based on the payload data and error-checking data received. If the amount of error or loss in a codeword is relatively small, the error-checking data can be used to recover the correct payload data.
Bursts of noise on the transmission media may cause the severity of data corruption in a codeword to be such that recovery is not possible. In order to reduce the impact of these bursts of noise, data interleaving techniques can be employed. By interleaving data from different codewords before transmission and de-interleaving the received data at the receiver, the impact of a burst of noise is spread over a number of different codewords, thus reducing the loss in each codeword to a level where recovery of the payload data in each codeword is possible.
The pattern of interleaving is controlled by two parameters. The first is the number of bytes of data in each codeword, which is represented by the number N. The second is the depth of interleaving to be performed, which is represented by the number D. Convolutional interleaving in ADSL requires that each of the N bytes B.sub.0, B.sub.1, . . ., B.sub.N-1 in a codeword be delayed by an amount that varies linearly with the byte index. Byte B.sub.i (the byte of the codeword with index i) is delayed by (D-1) * i bytes, where D is the interleave depth.
In order to interleave a data stream, memory is required to store the data from multiple codewords before transmission. If a particular byte is to be delayed by 20 bytes, the particular byte must be stored in memory for the next 20 transmissions before its turn to be transmitted arises. In one prior art technique described in the ADSL standard data is stored in memory in interleaved form and transmitted when completed interleaved codewords become available. The amount of memory required to perform the interleave function is equal to N * D bytes. It can be seen that as the number of bytes in a codeword and/or the depth of interleaving increases, the amount of memory required to store the interleaved data increases dramatically. Note that an equivalent amount of memory is required in the de-interleaver of the receiver, as data for different codewords will have to be stored until each de-interleaved codeword is complete.
The ANSI T1E1.4 (ADSL) committee has determined the parameters in an ADSL system regarding the size of each codeword (N) and the depth of interleaving (D). In a particular ADSL example, the size of each codeword (N) may be equal to 255 bytes, and the depth of interleaving (D) equal to 64. Thus, using prior art techniques, 255 * 64, or approximately 16K bytes of memory is required to interleave or de-interleave data. In integrated circuit (IC) implementations of data communications transmitters and receivers, these large memory blocks require a relatively large amount of die area, which increases the die size of the IC and the cost of the data communications system.
Therefore, in order to reduce die area and cost, a need exists for a method and apparatus to reduce the amount of memory required to perform interleave/de-interleaving of data in data communication systems.